package com.yangzhe.algorithm.c037;

// 验证搜索二叉树
// 测试链接 : https://leetcode.cn/problems/validate-binary-search-tree/

/**
 * 验证搜索二叉树
 * 有效 二叉搜索树定义如下：
 * <p>
 * 节点的左子树只包含 严格小于 当前节点的数。
 * 节点的右子树只包含 严格大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 * <p>
 * 测试链接 : https://leetcode.cn/problems/validate-binary-search-tree/
 */
public class Code05_ValidateBinarySearchTree_LeetCode {

    public static void main(String[] args) {
        TreeNode head = new TreeNode();
        head.val = 2;

        TreeNode node1 = new TreeNode();
        node1.val = 1;

        TreeNode node2 = new TreeNode();
        node2.val = 3;

        head.left = node1;
        head.right = node2;

        System.out.println(isValidBST1(head));
    }

    // 不提交这个类
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }


    private static TreeNode[] stack = new TreeNode[10001];

    /**
     * 提交时改名为isValidBST
     *
     * <p>
     * 前提：中序遍历二叉搜索树存在特性，会严格按照递增的顺序。
     * 方法1思路：中序遍历
     * 1. 中序遍历二叉树
     * 2. 和前一个打印的节点对比，如果比前一个小，则代表不是二叉搜索树
     * <p>
     * 时间复杂度：O(n)
     * 空间复杂度：O(h)，h 为树高（栈）
     */
    public static boolean isValidBST1(TreeNode head) {
        if (head == null) {
            return true;
        }
        int c = 0;
        long lastValue = Long.MIN_VALUE;

        while (head != null || c != 0) {
            if (head != null) {
                stack[c++] = head;
                head = head.left;
            } else {
                TreeNode node = stack[--c];

                if (node.val <= lastValue) {
                    return false;
                }

                lastValue = node.val;

                head = node.right;
            }

        }

        return true;
    }


    public static boolean isBst;


    /**
     * 提交时改名为isValidBST
     * <p>
     * 方法2思路：递归
     * 1. 搜索左树最大值，右树最小值
     * 2. 如果当前节点的值大于左子树最大值，小于右子树最小值
     * <p>
     * 时间复杂度：O(n)
     * 空间复杂度：O(h)，h 为树高（递归栈）
     */
    public static boolean isValidBST2(TreeNode head) {
        isBst = true;

        getExtremumValue(head);

        return isBst;
    }

    public static ExtremumValue getExtremumValue(TreeNode head) {
        ExtremumValue val = new ExtremumValue();
        if (head == null || !isBst) {
            return null;
        }

        ExtremumValue left = getExtremumValue(head.left);
        ExtremumValue right = getExtremumValue(head.right);

        long leftMax = Long.MIN_VALUE;
        long rightMin = Long.MAX_VALUE;

        if (left == null) {
            val.min = head.val;
        } else {
            leftMax = left.max;
            val.min = Math.min(head.val, left.min);
        }

        if (right == null) {
            val.max = head.val;
        } else {
            rightMin = right.min;
            val.max = Math.max(head.val, right.max);
        }


        if (head.val <= leftMax || head.val >= rightMin) {
            isBst = false;
            return null;
        }


        return val;
    }

    private static class ExtremumValue {
        public long max;
        public long min;
    }

}
